const maxCoins = (nums) => {
  const n = nums.length;
  // 添加两侧的虚拟气球
  const points = [1, ...nums, 1];
  // dp[i][j] 代表戳破气球 i 和气球 j 之间的所有气球可以获得的最大数
  const dp = Array.from(Array(n + 1), () => Array(n + 2).fill(0));
  for (let i = n; i >= 0; i--) {
    for (let j = i + 1; j < n + 2; j++) {
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          points[j] * points[k] * points[i] + dp[i][k] + dp[k][j]
        );
      }
    }
  }
  return dp[0][n + 1];
};
